'''
@Date 17 Jan 2013
@note: Exercise 12.2-2,12.2-3
'''

from tree import binary_tree
'''
Exercise 12.2-2
'''
def tree_min(root):
    if root.left == None:
        return root
    else:
        return tree_min(root.left)
def tree_max(root):
    if root.right == None:
        return root
    else:
        return tree_max(root.right)
        
        
'''
Exercise 12.2-3
'''
def tree_predecessor(root):
    if root.left!=None:
        return tree_max(root.left)
    y = root.parent
    while y!=None and root != y.right:
        root = y
        y = y.parent
    return y
    

#BST initialization
'''
        15(root)
      /  \
    6     18
   /\    /\
  3 7   17 20
 /\  \
2 4   13
     /
    9
'''
b_tree = binary_tree(15)

b_tree.insertAsLeftChild(15,6)
b_tree.insertAsRightChild(15,18)

b_tree.insertAsLeftChild(6,3)
b_tree.insertAsRightChild(6,7)
b_tree.insertAsLeftChild(18,17)
b_tree.insertAsRightChild(18,20)

b_tree.insertAsLeftChild(6,3)
b_tree.insertAsRightChild(6,7)

b_tree.insertAsLeftChild(3,2)
b_tree.insertAsRightChild(3,4)
b_tree.insertAsRightChild(7,13)

b_tree.insertAsLeftChild(13,9)

#TEST
#print tree_max(b_tree.root).value
#print tree_min(b_tree.root).value

print tree_predecessor(b_tree.getNode(15)).value#13
print tree_predecessor(b_tree.getNode(13)).value#9
print tree_predecessor(b_tree.getNode(7)).value#6
print tree_predecessor(b_tree.getNode(9)).value#7